package com.jn.algorithm.other.question99;

import java.util.Arrays;

/**
 * @author 江南大学1033190417
 * @date 2022/5/21 17:06
 */
public class Solution {
    public int minPathSum(int[][] grid) {
        //动态规划
        int m=grid.length;
        int n=grid[0].length;
        for(int i=1;i<m;i++){
            grid[i][0]+=grid[i-1][0];
        }
        for(int i=1;i<n;i++){
            grid[0][i]+=grid[0][i-1];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                grid[i][j]=Math.min(grid[i][j-1],grid[i-1][j])+grid[i][j];
            }
        }
        return grid[m-1][n-1];
    }

    public void print(int[][] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.println(Arrays.toString(arr[i]));
        }
    }


    public static void main(String[] args) {
        Solution solution=new Solution();
        int[][] nums=new int[][]{{1,2,3},{4,5,6}};
        System.out.println(solution.minPathSum(nums));
    }


}
